Packet networks such as Internet Protocol (IP) networks, multi-protocol label switched (MPLS) networks, or Ethernet networks are of increasing importance in next generation communications networks. Typically, and with reference to FIG. 1, a packet network 10 accepts traffic at an ingress gateway node 12 (or another such node 14, 16, 18, 20) from a source node outside the network 10 and destined for a destination node, via one of the other such nodes, for example, acting as an egress gateway node. A typical network comprises internal routers or switches 200, having interconnecting links 210 therebetween, over which data traffic is transmitted. Data progresses through the network on a hop by hop basis from router/switch to router/switch, as is well known in the art. A routing algorithm will be used to determine via which nodes and links in a network a data packet will progress across the network from an ingress gateway node to an egress gateway node.
A multi-service network is a network which uses the same network technology, such as IP, IP/MPLS, or Ethernet, for a variety of traffic classes. The available network capacity is shared between the different classes. A variety of systems and processes work together to ensure that contention between different service of traffic classes is dealt with appropriately and carried traffic in each individual class meets necessary requirements as captured in service level agreements relating to each class. Some of these systems and processes are defined for one particular service or traffic class. Examples are admission control systems for session-based services, and traffic engineering and bandwidth policing for VPN services. Other processes deal explicitly with the interaction between different service or traffic classes. Examples of such processes are queueing mechanisms (such as strict priority queueing or weighted fair queueing) which determine how packets belonging to different traffic classes are dealt with at each individual router or switch. Capacity planning, determining when and by how much to increase the capacity of certain network elements, can be viewed as a longer time-scale control process which affects the performance of all service classes.
Within the IETF, DiffServ, an architecture for offering differentiated services over IP networks, has been captured in RFC2475. Individual network operators can use DiffServ to guide the design of elements of their own multi-service networks.
FIG. 2 illustrates how the capacity of a link l between two network nodes 200 may be divided between multiple traffic classes. In this example the total link capacity K(l) is divided between three service or traffic classes, service A, service B, and service C. For example, each service class might relate to an individual VPN using the link. In this example, service A has allocated an amount of the capacity k(l, A), service B has allocated k(l, B), and service C has allocated k(l, c). Each service or traffic class, will typically have its own service level agreement specifying traffic characteristics and associated network transport charges. In this respect, as set out in RFC 2475, the term “service” encompasses a wide range of characteristics of packet transmission in one direction across a set of one or more paths within a network. These characteristics may be specified in quantitative or statistical terms of throughput, delay, jitter, and/or loss, or may otherwise be specified in terms of some relative priority of access to network resources. Service differentiation is desired to accommodate heterogeneous application requirements and user expectations, and to permit differentiated pricing of Internet service.
There are several existing proposals for managing traffic within a single service class in a network where the capacity allocated to that service class is already determined that make use of so called “congestion prices”. Generally, congestion prices are defined for individual links and increase as the link's utilisation increases. One example of a traffic management proposal that makes use of congestion prices is the rate control scheme for elastic (best effort) traffic described in Frank Kelly, Aman Maulloo and David Tan: “Rate control in communication networks: shadow prices, proportional fairness and stability”, Journal of the Operational Research Society 49 (1998) 237-252. In this scheme, the congestion prices of all links that are (considered to be) used by a particular flow or session are added to obtain a total cost. This total cost is used to determine how to adjust the flow rates (increase for low costs, decrease for high costs).
Another example use of congestion prices are the arrangements described in our earlier International patent applications WO09/122150 and WO09/122152. These applications describe a joint multi-path routing and admission control scheme for guaranteed, session-based services, wherein the link congestion prices are used to determine which, if any, of the available paths to use for a session (by selecting the path with lowest cost and admitting the session to that path if the cost is sufficiently low).
In terms of service or traffic class capacity determination, however, the resource control schemes discussed above assume that service or traffic class capacity has been fixed in advance at a particular level, for example by network planners. In this respect, the congestion pricing functions used require a given link capacity, and operate with the objective that flow rate or admission is controlled such that the given capacity is not exceeded—the congestion price typically approaches infinity (or a high value) at the provided capacity, such that total capacity utilisation is not usually achieved. In this respect, in the schemes discussed above, the congestion price is interpreted as a cost incurred for using a unit of the capacity allocated to the considered service class, with that cost increasing as the available capacity reduces.
In another article entitled “Achieving optimal revenues in dynamically priced network services with QoS guarantees” by Steven Shelford et al (Computer Network vol. 51 (2007), pages 3294-3304), the problem is considered of a single Internet Service Provider (ISP) determining the bandwidth to allocate to each of a number of dynamically priced network services, and on which path, in order to maximize revenue while guaranteeing end-to-end quality of service (QoS). No knowledge of demand functions is assumed. Optimal allocation of bandwidth to services is first considered, where services are assumed to be routed on predetermined paths. An Iterative Allocation Adjustment heuristic is defined, based on the concepts of “tatonnement” (an iterative process where prices are adjusted until supply equals demand). There is also a discussion of how to value links in the network to identify re-routing possibilities, or possible routes for new services, in order to improve the revenue of an ISP.